$\mathrm{C}\mathrm{C}\mathrm{S}$
に基づく並列処理言語の実装
九州大学システム情報科学研究科 原淳 (Atsushi Hara) 九州大学システム情報科学研究科 森雅生 (Masao Mori)1
はじめに
ここ数年の間に並列コンピュータや並列/分散処理機構を備えた計算機ネットワーク(これらをまとめ て並列/分散コンピュータ と呼ぶ) が目覚しく発達してきた. それを用いて 1 台のコンピュータでは処理しきれないような大きいデータを,ほとんど通常のプログラム 言語を使っているのと変わらないような感覚で分散/並列計算を行なうプログラムを記述することを目的と して,CCS[2] が提案している並列プログラム言語の意味論を基礎に改良した並列分散プログラム言語を定 義し, 実装した.2
$\overline{\equiv}-$語の定義
言語は,C 言語やPASCAL 言語風の手続き型言語に並列演算子 (Par) を付け加えたものとし, 文法を以 下のように定義した. $X$ $::=:$ $X|Y|\cdots$ 変数 $F$ $::=$ $+|-|\cdot,$.
$|0|1|\cdots$ 関数 $C$ $::=$ $C,$ $C’$ 直列合成 $X:=E$ 代入 if$(E)\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\{Dv;c\}\mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}\{D_{v}’;c’\}$ 条件分岐 while$(E)\mathrm{d}\mathrm{o}\{D_{v} ; c\}$ 繰り返し $\{D. ;c\}_{\mathrm{P}^{\mathrm{a}\mathrm{r}}}\{D_{v}l;c^{J}\}$ 並列合成 call $\mathrm{G}(E, Z)$ 手続き呼び出し input X 入力 output $\mathrm{E}$ 出力 $D_{v}$ $::=$ $D_{v}$;$D_{v}’$ var X 変数宣言 $D_{p}$ $::=$ $D_{p}$;$D_{\iota}’$proc $\mathrm{G}$(in $X$;out $Y$)$\mathrm{i}\mathrm{s}\{D_{v} ; C\}$ 手続き
$E$ $::=$ $X$ 変数
$F(E_{1}, E_{2}, \cdots, E_{n})$ 関数適用
定義した言語を実装するために, 並列言語からCCSの言語への変換の関数$M[-]$ を次のように定義した.
数理解析研究所講究録
$M[C;c]$ $=$ $M[C]Bef_{\mathit{0}}reM[CJ]$
$M[X:=E]$ $=$ $\overline{up}_{X}.M[E]Into(x)$($\overline{put_{X}}X.\overline{down}X\cdot$Done)
$M[\mathrm{i}\mathrm{f}(E)\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}\{Dv;c\}\mathrm{e}\mathrm{l}\mathrm{S}\mathrm{e}\{D’;vc’\}]$ $=$ $M[E]Into(X)(\mathrm{i}\mathrm{f}X\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{m}M[D_{v};c_{]}\mathrm{e}\mathrm{l}\mathrm{s}\mathrm{e}M[D_{v}’;c’])$
$M[\mathrm{w}\mathrm{h}\mathrm{i}\mathrm{l}\mathrm{e}(E)\mathrm{d}\mathrm{o}\{D;vC\}]$ $=$ $W$ , where $W=Mdef[E]Int_{o(}X)$
($\mathrm{i}\mathrm{f}x\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{n}M[D_{v}$;$c]$
Before
Welse done)$M[\{D_{v};c\}\mathrm{p}\mathrm{a}\mathrm{r}\{D_{v}’\} ; c^{J}]$ $=$ $M[D_{v};C]ParM[D’;vc^{J}]$ $M[\mathrm{i}\mathrm{n}_{\mathrm{P}^{\mathrm{u}\mathrm{t}}}\mathrm{X}]$ $=$ $\overline{up}_{X}.inx.\overline{putx}x.\overline{down}\mathrm{x}\cdot Done$ $M[\mathrm{o}\mathrm{u}\mathrm{t}_{\mathrm{P}}\mathrm{u}\mathrm{t}\mathrm{E}]$ $=$ $M[E]Into(X)(\overline{out}X.Done)$ $M[\{D_{v};C\}]$ $=$ $(M[D_{v}]|M[C])\backslash ACCDv$ $M$[$\mathrm{v}\mathrm{a}\mathrm{r}$ X] $=$ $Semx|LocX$ $M[\mathrm{c}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{G}(E, Z)]$ $=$ $M[E]Into(X).(namecg_{C}.\overline{all_{G,g}}X.returnc,gz.\overline{put_{z}}Z.Done)$
$M$[$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{G}(inx,$outY) is $D_{v}$;$C$] $=$ $W(\mathrm{O})$ , where
$W(g)$ $de=^{f}$
$\overline{name_{Gg}}.(G_{g}|W(g+1))$
$G_{g}$
$de=^{f}$
$Callc,g^{X.(L|Lo}ocXc\mathrm{Y}|\overline{put_{x}}x.M[Dv;C].get\mathrm{Y}y.\overline{returnc_{g},}y.\mathrm{o})\backslash L_{X}\backslash L_{\mathrm{Y}}$
$M[X]$ $=$ $getxX.\overline{reS}x.0$
$M[F(E_{1_{)}}\cdots , E_{n})]$ $=$ $(M[E_{1}][arg_{1}/res]|\cdots|M[E_{n}][arg_{n}/res]$
$|M[F])\backslash$
{
$arg1,$$\cdots,$argn}
$M[F]$ $=$ $arg_{1^{X_{1}.\cdots.ar}}gnx_{n}.\overline{res}(f(X_{1}, \cdots, X_{n})).0$
ここで,
Done $def=$ $\overline{done}.0$
$P$
Before
$Q$ $de=^{f}$ $(P[b/done]|b.Q)\backslash b$ $P$ Par $Q$ $def=$ $(P[d_{1}/done]|Q[d_{2/}done]|$$(d_{1}.d_{2}.Done+d_{2}.d_{1}.D_{on}e))\backslash \{d1, d_{2}\})$ $PInto(x)Q$ $dej=$ $(P|res(X).Q)\backslash res$ この変換関数は, 文献[2] で定義されているものを基礎に改良したものになっている. 特に, 手続き呼び 出しに関しては, 実装時の効率を考えて大幅に変更を行なった. 手続き起動プロセス 文献[2] で行なわれている定義では,
手続きプロセスは常に
1
個以上が呼び出し待ち状態にあるため
,
メ モリの使用効率が落ち, また手続きプロセスの生成, 消滅毎に変数プロセス以外の全てのプロセスに呼び出 し可能なプロセスのプロセス IDを通知しなければならず不必要な通信が行われるため,
それぞれの手続き プロセスについて手続き起動プロセスを作り, 手続き呼び出しはそれを通して行なうようにした. この場合, 手続き呼び出しは呼出側が, 手続き起動プロセスと通信して, 新たに生成された手続きプロ セスの番号を受けとり, この番号を用いて手続きの呼び出しを行なうようになっている. 手続き起動プロセスは, 式の $W(n)$ にあたる.123
図 1: 手続き起動プロセス
3
言語の実装
2節で定義した言語の仕様に基づいて実装を行った. コンパイラは, 並列言語のソースプログラムから$\mathrm{C}$言語への変換プログラムと, 変換されたプログラムを コンパイルするときに必要となる通信関係のライブラリからなっている. また, 作成したプログラムで共通して使用するプロセスの作成も行った. $\mathrm{C}$言語への変換にはPerl を, 通信にはPVM を用いている.3.1
PVM
の概要
$\mathrm{P}\mathrm{V}\mathrm{M}$(Parallel Virtual $\mathrm{M}\mathrm{a}\mathrm{c}\mathrm{i}\mathrm{n}\mathrm{e}$)$[1]$
は, ネットワークに接続された異機種$\mathrm{U}\mathrm{N}$ IXコンピュータ群を,単 の並列コンピュータとして利用することを可能とするソフトウェアシステムである. PVM のシステムの構成は, 以下の2つに分けられる. デーモン分散メモリ型並列コンピュータを構成する全てのコンピュータ上に常駐し, 実際の通信等を行 なう. ライブラリ PVM が提供する機能へのインタフェイスルーチンのライブラリであり,PVM を利用するアプ リケーションは, このライブラリをリンクする必要がある. ライブラリへの言語インタフェイスとしては,C言語と Fortran 言語が用意されており,今回は$\mathrm{C}$言語を 用いた. PVM では, 各プロセスにタスクID と呼ばれる番号がついており, プロセス間の通信では, これを用いて 相手の指定をする. 言語の実装には,PVM により提供される機能のうち, プロセスの生成/消滅, プロセス間の通信の機能を 利用している.
3.2
実装にともなう変更
実装では, 前節の定義では不都合な部分が出てきたため, -部変更を行ない, 新たにプログラム起動/ 終了プロセスを追加した.124
プログラム起動/終了プロセス プログラム全体は, 標準入出力を行なうプロセスをStdio として, $M\mathrm{r}P^{ro}g]=M[D_{v} ; D_{p}; C]=M[D_{v}]|M[D_{p}]|M[C]|$Stdio と書くことができるが, ここまでの定義のままでは, プログラムを終了したとき, Cの部分のプロセス は終了して消えるが, $D_{v},$ $D_{p}$の部分のプロセスは, 終了しない. このため, プログラム全体を終了させる ために, C が終了した時点で全てのプロセスを終了させる部分を追加して,
$M\mathrm{r}_{P^{ro}g}]=M[D_{v} ; D_{p}; C]=M[D_{v}]|M[D_{p}]|M[C]$
Before
Killall $|$ Stdioとした. この, 残ったプロセスを終了させるプロセスと, 標準入出力の部分をまとめてプログラム起動プロセス とした. このプロセスはそれ以外に, 全域変数のプロセス, 手続きのプロセス, プログラム本体のプロセ スを起動と, 起動した各プロセスへのタスク $\mathrm{I}\mathrm{D}$ の通知をおこなっている.
4
まとめ
本論分では,CCSが提案している並列プログラム言語の意味論を基礎に改良し並列プログラム言語を定
義,実装した. 実装した言語は,最低限の機能しか持たないものであり, また,1 変数を扱うにも負数キロバイトものメモ リを消費し, 手続きの再帰呼び出しを行なうときに, 毎回同じプロセスをたちあげるなど非常に効率の悪い ものであった. 今後は, 変数に関しては,プロセスローカルに扱えるものは変数プロセスを用いないようにして速度,
メ モリの効率を向上し,非ローカルな変数に関しても,ICPU につき1
個のプロセスで変数を管理するような,
変数マネージャープロセスを用いることによってメモリ効率の向上を行ないたい. さらに, 配列や, 実数変数 の実装も行ないたい.参考文献
[1] Al Geistet $\mathrm{a}\mathrm{l},$”$\mathrm{P}\mathrm{V}\mathrm{M}:\mathrm{P}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{l}$Virtual Macine”,The MIT Press,
1994.
[2] Robin $\mathrm{M}\mathrm{i}\mathrm{l}\mathrm{n}\mathrm{e}\mathrm{r},\mathrm{c}_{0}$
)) $\mathrm{m}\mathrm{m}\mathrm{u}\mathrm{n}\mathrm{i}_{\mathrm{C}}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$ and Cocurrency”,Prentice Hall, 1989.
